package LCR;

public class quick_sort_dig {
    public static void main(String[] args) {
        int[] ret = new int[]{5, 7, 9, 1, 3, 2, 8};
        quick_sort_dig(ret,0,ret.length-1);
        for (int x :
                ret) {
            System.out.print(x + " ");
        }
    }

    static void quick_sort_dig(int[] nums,int start,int end) {
        if(start < end){
            int dig = nums[start];//坑
            int left = start;//左指针
            int right = end;//右指针
            while (left < right) {
                while (left < right && nums[right] >= dig) {
                    right--;
                }
                //nums[right]比base小，替换left所在位置数字
                nums[left] = nums[right];

                while (left < right && nums[left] <= dig) {
                    left++;
                }
                //nums[left]比base大，替换right所在位置数字
                nums[right] = nums[left];
            }
            nums[left] = dig;
            //对base左侧数组进行排序
            quick_sort_dig(nums,start,left-1);
            //对base右侧数组进行排序
            quick_sort_dig(nums,left+1,end);
        }

    }

}
